from typing import *


class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        u, l = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    u[i][j] = u[i - 1][j] + 1 if i > 0 else 1
                    l[i][j] = l[i][j - 1] + 1 if j > 0 else 1
                else:
                    u[i][j] = u[i - 1][j] if i > 0 else 0
                    l[i][j] = l[i][j - 1] if j > 0 else 0
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans += (
                        (u[i][j] - 1) * (l[i][j] - 1)
                        + (u[i][j] - 1) * (l[i][n - 1] - l[i][j])
                        + (l[i][n - 1] - l[i][j]) * (u[m - 1][j] - u[i][j])
                        + (u[m - 1][j] - u[i][j]) * (l[i][j] - 1)
                    )

        return ans


s = Solution()
print(s.numberOfRightTriangles([[0, 1, 0], [0, 1, 1], [0, 1, 0]]))
